package leetcode.editor.week.week312;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

// 6190. 找到所有好下标
// https://leetcode.cn/problems/find-all-good-indices/
public class Solutio6190 {
    // https://leetcode.cn/problems/find-all-good-indices/solution/-by-universe-explorer-go9y/
    public List<Integer> goodIndices(int[] nums, int k) {
        int n = nums.length;
        // incr表示包括第i位前面连续递增的个数
        // decr表示包括第i位前面连续递减的个数
        int[] incr = new int[n], decr = new int[n];
        // 包括本身，所以可以都赋值为1
        Arrays.fill(incr, 1);
        Arrays.fill(decr, 1);
        for (int i = 1; i < n; i++) {
            if (nums[i] <= nums[i - 1]) incr[i] = incr[i - 1] + 1;
        }

        for (int i = n - 2; i >= 0; i--) {
            if (nums[i] <= nums[i + 1]) decr[i] = decr[i + 1] + 1;
        }

        List<Integer> res = new ArrayList<>();
        // 对于i，需要满足incr[i - 1]的值比k大，且decr[i + 1]的值也比k大
        for (int i = k; i < n - k; i++) {
            if (incr[i - 1] >= k && decr[i + 1] >= k) {
                res.add(i);
            }
        }

        return res;
    }
}
